package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class No54 {
    public static void main(String[] args) {
        int[][] a ={{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(spiralOrder(a));
    }
    public static List<Integer> spiralOrder(int[][] matrix) {
        int top = 0,left=0,right=matrix[0].length,bottom=matrix.length;

        List<Integer> list = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[][] value = new boolean[m][n];    //是否遍历过，true为遍历过
        int nextRow = 0,nextColumn =0;    //下一个访问的行列
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};     //代表四个遍历方向，右下左上
        int row = 0,column=0;     //当前遍历的数的行列
        int total = m*n;      //总数
        int directionIndex = 0;       //当前遍历方向
        for (int i = 0; i < total; i++) {
            list.add(matrix[row][column]);
            value[row][column] = true;
            nextRow= row+directions[directionIndex][0];       //计算下一个遍历的行
            nextColumn = column+directions[directionIndex][1];        //计算下一个遍历的列
            if(nextRow<0||nextRow>=m||nextColumn<0||nextColumn>=n||value[nextRow][nextColumn]) {      //到最上了，到最下了，到最右了，到最左了，访问过了
                directionIndex = (directionIndex+1)%4;    //换下一个方向
            }
            row+=directions[directionIndex][0];
            column+=directions[directionIndex][1];
        }
        return list;
    }
}
